package com.lw.leetcode.binary.c;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * binary
 * 2258. 逃离火灾
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/23 13:58
 */
public class MaximumMinutes {

    public static void main(String[] args) {
        MaximumMinutes test = new MaximumMinutes();

        // 3
//        int[][] grid = {{0, 2, 0, 0, 0, 0, 0}, {0, 0, 0, 2, 2, 1, 0}, {0, 2, 0, 0, 1, 2, 0}, {0, 0, 2, 2, 2, 0, 2}, {0, 0, 0, 0, 0, 0, 0}};

        // -1
//        int[][] grid = {{0, 0, 0, 0}, {0, 1, 2, 0}, {0, 2, 0, 0}};

        // 0
//        int[][] grid = {{0, 0, 0}, {2, 2, 0}, {1, 2, 0}};

        // 1000000000
        int[][] grid = {{0, 2, 0, 0, 1}, {0, 2, 0, 2, 2}, {0, 2, 0, 0, 0}, {0, 0, 2, 2, 0}, {0, 0, 0, 0, 0}};

        //
//        int[][] grid = Utils.getArr(200, 100, 0, 1);

        int i = test.maximumMinutes(grid);
        System.out.println(i);
    }

    private int[][] grid;
    private int[][] arr = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int m;
    private int n;

    public int maximumMinutes(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            int[] ints = grid[i];
            int t = i * n;
            for (int j = 0; j < n; j++) {
                int v = ints[j];
                if (v == 1) {
                    list.add((t + j) << 16);
                    ints[j] = 0;
                } else if (v == 2) {
                    ints[j] = -2;
                } else {
                    ints[j] = -1;
                }
            }
        }
        while (!list.isEmpty()) {
            int p = list.poll();
            int index = p >> 16;
            int count = p & 0XFFFF;
            int x = index / n;
            int y = index % n;
            for (int[] ints : arr) {
                int a = x + ints[0];
                int b = y + ints[1];
                if (a < 0 || b < 0 || a == m || b == n) {
                    continue;
                }
                if (grid[a][b] == -1) {
                    grid[a][b] = count + 1;
                    list.add(((a * n + b) << 16) + count + 1);
                }
            }
        }
        if (grid[m - 1][n - 1] == -1) {
            if (grid[0][0] > 0) {
                return -1;
            }
            list.add(0);
            grid[0][0] = -3;
            while (!list.isEmpty()) {
                int p = list.poll();
                int x = p >> 16;
                int y = p & 0XFFFF;
                for (int[] ints : arr) {
                    int a = x + ints[0];
                    int b = y + ints[1];
                    if (a < 0 || b < 0 || a == m || b == n) {
                        continue;
                    }
                    if (grid[a][b] == -1) {
                        grid[a][b] = -3;
                        list.add((a << 16) + b);
                    }
                }
            }
            return grid[m - 1][n - 1] == -3 ? 1000000000 : -1;
        }
        int st = 0;
        int end = grid[m - 1][n - 1];
        Set<Integer> set = new HashSet<>();
        while (st < end) {
            int mid = st + ((end - st + 1) >> 1);
            if (find(mid, list, set)) {
                st = mid;
            } else {
                end = mid - 1;
            }
            set.clear();
            list.clear();
        }
        return find(st, list, set) ? st : -1;

    }

    private boolean find(int mid, LinkedList<Integer> list, Set<Integer> set) {
        if (grid[0][0] <= mid) {
            return false;
        }
        list.add(mid);
        set.add(0);
        while (!list.isEmpty()) {
            int p = list.poll();
            int index = p >> 16;
            int count = p & 0XFFFF;
            int x = index / n;
            int y = index % n;
            for (int[] ints : arr) {
                int a = x + ints[0];
                int b = y + ints[1];
                if (a < 0 || b < 0 || a == m || b == n) {
                    continue;
                }
                int t = a * n + b;
                if (set.contains(t)) {
                    continue;
                }
                set.add(t);
                if (grid[a][b] >= count + 1) {
                    if (a == m - 1 && b == n - 1) {
                        return true;
                    }
                    if (grid[a][b] > count + 1) {
                        list.add((t << 16) + count + 1);
                    }
                }
            }
        }
        return false;
    }

}
